<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>单词拆分 - 动态规划算法详解</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
        }
        .serif-font {
            font-family: 'Noto Serif SC', serif;
        }
        .gradient-text {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            -webkit-background-clip: text;
            -webkit-text-fill-color: transparent;
            background-clip: text;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-4px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        .code-block {
            background: #1e1e1e;
            border-radius: 12px;
            overflow: hidden;
        }
        .code-header {
            background: #2d2d2d;
            padding: 12px 20px;
            display: flex;
            align-items: center;
            justify-content: space-between;
        }
        .code-dots {
            display: flex;
            gap: 8px;
        }
        .dot {
            width: 12px;
            height: 12px;
            border-radius: 50%;
        }
        .dot-red { background: #ff5f56; }
        .dot-yellow { background: #ffbd2e; }
        .dot-green { background: #27c93f; }
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
        }
        code {
            font-family: 'Consolas', 'Monaco', 'Courier New', monospace;
            font-size: 14px;
            line-height: 1.6;
            color: #d4d4d4;
        }
        .keyword { color: #569cd6; }
        .string { color: #ce9178; }
        .comment { color: #6a9955; }
        .function { color: #dcdcaa; }
        .number { color: #b5cea8; }
        .drop-cap {
            float: left;
            font-size: 4rem;
            line-height: 1;
            font-weight: 700;
            margin-right: 0.5rem;
            margin-top: -0.1rem;
            color: #667eea;
        }
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
        @keyframes fadeIn {
            from { opacity: 0; transform: translateY(20px); }
            to { opacity: 1; transform: translateY(0); }
        }
        .fade-in {
            animation: fadeIn 0.8s ease-out;
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-6">
        <div class="max-w-4xl mx-auto text-center fade-in">
            <h1 class="text-5xl md:text-6xl font-bold mb-6 serif-font">单词拆分</h1>
            <p class="text-xl md:text-2xl mb-8 opacity-90">动态规划算法的优雅实现</p>
            <div class="flex justify-center gap-6 text-sm">
                <span class="flex items-center gap-2">
                    <i class="fas fa-clock"></i>
                    时间复杂度 O(n²)
                </span>
                <span class="flex items-center gap-2">
                    <i class="fas fa-memory"></i>
                    空间复杂度 O(n)
                </span>
                <span class="flex items-center gap-2">
                    <i class="fas fa-tag"></i>
                    动态规划
                </span>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-6xl mx-auto px-6 py-12">
        <!-- Problem Description -->
        <section class="mb-16 fade-in">
            <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                <h2 class="text-3xl font-bold mb-6 flex items-center gap-3">
                    <i class="fas fa-puzzle-piece text-purple-600"></i>
                    <span class="gradient-text">题目描述</span>
                </h2>
                <div class="prose prose-lg max-w-none">
                    <p class="text-gray-700 leading-relaxed">
                        <span class="drop-cap serif-font">给</span>定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判断 s 是否可以被空格拆分为一个或多个在字典中出现的单词。每个单词可以重复使用。
                    </p>
                    <div class="mt-6 p-6 bg-purple-50 rounded-xl border-l-4 border-purple-600">
                        <h3 class="font-semibold text-lg mb-3 text-purple-900">示例</h3>
                        <div class="space-y-2">
                            <p class="text-gray-700">
                                <span class="font-mono bg-gray-100 px-2 py-1 rounded">输入：</span> 
                                s = "leetcode", wordDict = ["leet", "code"]
                            </p>
                            <p class="text-gray-700">
                                <span class="font-mono bg-gray-100 px-2 py-1 rounded">输出：</span> 
                                true
                            </p>
                            <p class="text-gray-600 text-sm mt-2">
                                <i class="fas fa-info-circle"></i> 
                                解释："leetcode" 可以被拆分成 "leet code"
                            </p>
                        </div>
                    </div>
                </div>
            </div>
        </section>

        <!-- Algorithm Visualization -->
        <section class="mb-16 fade-in">
            <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                <h2 class="text-3xl font-bold mb-6 flex items-center gap-3">
                    <i class="fas fa-sitemap text-purple-600"></i>
                    <span class="gradient-text">算法可视化</span>
                </h2>
                <div class="mermaid">
                    graph TD
                        A[开始] --> B[初始化 dp 数组]
                        B --> C[dp[0] = true]
                        C --> D[遍历字符串每个位置 i]
                        D --> E{检查所有拆分点 j}
                        E -->|dp[j] = true| F[检查 s[j:i] 是否在字典中]
                        F -->|是| G[dp[i] = true]
                        F -->|否| H[继续下一个 j]
                        G --> I[继续下一个 i]
                        H --> E
                        I --> D
                        D -->|遍历完成| J[返回 dp[n]]
                        
                        style A fill:#667eea,stroke:#fff,color:#fff
                        style J fill:#764ba2,stroke:#fff,color:#fff
                        style G fill:#27c93f,stroke:#fff,color:#fff
                </div>
            </div>
        </section>

        <!-- Solution Approach -->
        <section class="mb-16 fade-in">
            <div class="grid md:grid-cols-2 gap-8">
                <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                    <h3 class="text-2xl font-bold mb-4 flex items-center gap-3">
                        <i class="fas fa-lightbulb text-yellow-500"></i>
                        核心思路
                    </h3>
                    <ul class="space-y-4">
                        <li class="flex items-start gap-3">
                            <span class="text-purple-600 mt-1">
                                <i class="fas fa-check-circle"></i>
                            </span>
                            <div>
                                <p class="font-semibold">状态定义</p>
                                <p class="text-gray-600">dp[i] 表示字符串 s 的前 i 个字符是否可以被拆分</p>
                            </div>
                        </li>
                        <li class="flex items-start gap-3">
                            <span class="text-purple-600 mt-1">
                                <i class="fas fa-check-circle"></i>
                            </span>
                            <div>
                                <p class="font-semibold">状态转移</p>
                                <p class="text-gray-600">若存在 j < i 使得 dp[j] = true 且 s[j:i] 在字典中，则 dp[i] = true</p>
                            </div>
                        </li>
                        <li class="flex items-start gap-3">
                            <span class="text-purple-600 mt-1">
                                <i class="fas fa-check-circle"></i>
                            </span>
                            <div>
                                <p class="font-semibold">初始状态</p>
                                <p class="text-gray-600">dp[0] = true，表示空字符串可以被拆分</p>
                            </div>
                        </li>
                    </ul>
                </div>

                <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                    <h3 class="text-2xl font-bold mb-4 flex items-center gap-3">
                        <i class="fas fa-chart-line text-green-500"></i>
                        复杂度分析
                    </h3>
                    <div class="space-y-6">
                        <div>
                            <h4 class="font-semibold text-lg mb-2 flex items-center gap-2">
                                <i class="fas fa-clock text-blue-500"></i>
                                时间复杂度
                            </h4>
                            <p class="text-gray-600">O(n²)，其中 n 是字符串 s 的长度</p>
                            <p class="text-sm text-gray-500 mt-1">需要两层循环遍历所有可能的拆分点</p>
                        </div>
                        <div>
                            <h4 class="font-semibold text-lg mb-2 flex items-center gap-2">
                                <i class="fas fa-memory text-purple-500"></i>
                                空间复杂度
                            </h4>
                            <p class="text-gray-600">O(n)，用于存储 dp 数组</p>
                            <p class="text-sm text-gray-500 mt-1">额外使用 HashSet 存储字典，空间为 O(m)</p>
                        </div>
                    </div>
                </div>
            </div>
        </section>

        <!-- Code Implementation -->
        <section class="mb-16 fade-in">
            <div class="bg-white rounded-2xl shadow-lg overflow-hidden card-hover">
                <div class="p-8 pb-0">
                    <h2 class="text-3xl font-bold mb-6 flex items-center gap-3">
                        <i class="fas fa-code text-purple-600"></i>
                        <span class="gradient-text">代码实现</span>
                    </h2>
                </div>
                <div class="code-block mx-8 mb-8">
                    <div class="code-header">
                        <div class="code-dots">
                            <span class="dot dot-red"></span>
                            <span class="dot dot-yellow"></span>
                            <span class="dot dot-green"></span>
                        </div>
                        <span class="text-gray-400 text-sm">Java</span>
                    </div>
                    <pre><code><span class="keyword">public boolean</span> <span class="function">wordBreak</span>(<span class="keyword">String</span> s, <span class="keyword">List</span>&lt;<span class="keyword">String</span>&gt; wordDict) {
    <span class="comment">// 将单词列表转换为HashSet以便快速查找</span>
    <span class="keyword">Set</span>&lt;<span class="keyword">String</span>&gt; wordSet = <span class="keyword">new</span> <span class="function">HashSet</span>&lt;&gt;(wordDict);
    
    <span class="comment">// 创建动态规划数组，dp[i]表示字符串s的前i个字符是否可以被拆分</span>
    <span class="keyword">boolean</span>[] dp = <span class="keyword">new boolean</span>[s.<span class="function">length</span>() + <span class="number">1</span>];
    
    <span class="comment">// 空字符串可以被拆分</span>
    dp[<span class="number">0</span>] = <span class="keyword">true</span>;
    
    <span class="comment">// 遍历字符串的每个位置</span>
    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= s.<span class="function">length</span>(); i++) {
        <span class="comment">// 检查所有可能的拆分点</span>
        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; i; j++) {
            <span class="comment">// 如果前j个字符可以被拆分，且j到i的子串在字典中存在</span>
            <span class="